package leetcodev1.字符串;

import leetcodev1.链表.Solution;

import java.util.*;

public class LeetCode17 {

    //error 超出空间限制
    Map<Character, Character[]> dict = new HashMap<Character, Character[]>() {{
        put('2', new Character[]{'a', 'b', 'c'});//用string存更好一点
        put('3', new Character[]{'d', 'e', 'f'});
        put('4', new Character[]{'g', 'h', 'i'});
        put('5', new Character[]{'j', 'k', 'l'});
        put('6', new Character[]{'m', 'n', 'o'});
        put('7', new Character[]{'p', 'q', 'r', 's'});
        put('8', new Character[]{'t', 'u', 'v'});
        put('9', new Character[]{'w', 'x', 'y', 'z'});
    }};

    //动态规划
    //回溯可以减少中间过程产生的空间浪费
    public List<String> letterCombinations(String digits) {
        if (digits.equals("")) {
            return new ArrayList<>();
        }

        int length = digits.length();
        List<String> ret = new ArrayList<>();
        List<String> tmp = new ArrayList<>();
        for (char c : dict.get(digits.charAt(0))) {
            ret.add("" + c);
        }

        for (int i = 1; i < length; i++) {
            Character[] characters = dict.get(digits.charAt(i));
            for (int j = 0; j < ret.size(); j++) {
                for (char c : characters) {
                    tmp.add(ret.get(j) + c);
                }
            }
            ret = tmp;
        }
        return ret;
    }
}

class Answer17 {
    //使用回溯可以节约空间
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());//copy
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);//回溯可以直接根据index删除
            }
        }
    }
}
